package _220326;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author ShadowLim
 * @create 2022-03-26-9:32
 */

/**
 * 参考：https://blog.csdn.net/lishifu_/article/details/123696818
 */
public class 估计人数 {
    static int n, m;
    static int[][] map;         // 模拟矩阵的状态
    static boolean[][] conn;    // 判断两点是否可以连接
    static boolean[] vis;
    static int[] match;         // 匹配图
    static int sum = 1;         // 可访问点的数量

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        map = new int[n][m];
        for (int i = 0; i < n; i++) {
            String s = scanner.next();
            for (int j = 0; j < m; j++) {
                if (s.charAt(j) == '1') {
                    map[i][j] = sum++;
                }
            }
        }
        conn = new boolean[sum][sum];
        vis = new boolean[sum];
        match = new int[sum];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 当前位置和下方位置都大于0，表示可以连接
                if (map[i][j] > 0 && i + 1 < n && map[i + 1][j] > 0) {
                    conn[map[i][j]][map[i + 1][j]] = true;
                }
                // 当前位置和右侧位置都大于0，表示可以连接
                if (map[i][j] > 0 && j + 1 < n && map[i][j + 1] > 0) {
                    conn[map[i][j]][map[i][j + 1]] = true;
                }
            }
        }

        // Floyd
        for (int i = 1; i < sum; i++) {
            for (int j = 1; j < sum; j++) {
                for (int k = 1; k < sum; k++) {
                    if (conn[j][i] && conn[i][k] && j != k) {
                        conn[j][k] = true;
                    }
                }
            }
        }

        int num = 0;
        // 匈牙利算法，最坏情况的时间复杂度为O(n^3)
        for (int i = 1; i < sum; i++) {
            Arrays.fill(vis, true);
            if (dfs(i)) {
                num++;
            }
        }
        // 最小路径覆盖 = 结点数 - 最大匹配数
        System.out.println(sum - num - 1);
    }

    private static boolean dfs(int i) {
        for (int j = 1; j < sum; j++) {
            // 点i与点j进行匹配，点i必须和点j可以连接 且点j可以被访问
            if (conn[i][j] && vis[j]) {
                vis[j] = false;
                // 如果点j没有匹配对象，点i就和点j进行匹配，直接返回true
                // 如果点j有匹配对象，假设点j的匹配对象是点k
                // 我们开始寻找点k的匹配对象
                // 如果点k可以找到其他的匹配对象，那就让点k和它进行匹配
                // 点i横刀夺爱匹配点j
                // 如果点k不能找到其他的匹配对象，点i就不能和点j进行匹配，不能让点k打光棍
                if (match[j] == 0 || dfs(match[j])) {
                    match[j] = i;
                    return true;
                }
            }
        }
        return false;
    }
}
